Fast algorithms inspired by Physarum polycephalum for node weighted steiner tree problem with multiple terminals

Abstract

Recently it has been shown that Physarum-inspired algorithms can solve some network optimization problems. However, it is not yet shown that Physarum-inspired algorithm can solve Node Weighted Steiner Tree Problem (NWSTP). Two new Physarum-inspired algorithms are proposed in this paper to solve NWSTP for the first time. Since all the existing NWSTP benchmark instances have an empty terminal set, new benchmark instances with non-empty terminal sets are generated to cover the shortage of existing benchmark instances. Both proposed algorithms are compared with Genetic Algorithm (GA) and Discrete Particle Swarm Optimization (DPSO) in these benchmark instances. Furthermore, an adapted Dijkstra's ..